function maxSubArray(nums: number[]): number {
    if (nums.length === 0) return 0;

    let maxSum = nums[0];
    let currentSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
        // 选择：要么加入当前元素，要么从当前元素重新开始
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        // 更新全局最大值
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

// 分治法
function maxSubArrayDivideAndConquer(nums: number[]): number {
    return divideAndConquer(nums, 0, nums.length - 1);
}

function divideAndConquer(nums: number[], left: number, right: number): number {
    // 基准情况：只有一个元素
    if (left === right) {
        return nums[left];
    }

    const mid = Math.floor((left + right) / 2);

    // 递归求解左右子数组的最大子数组和
    const leftMax = divideAndConquer(nums, left, mid);
    const rightMax = divideAndConquer(nums, mid + 1, right);

    // 计算跨越中点的最大子数组和
    const crossMax = maxCrossingSum(nums, left, mid, right);

    // 返回三者中的最大值
    return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSum(nums: number[], left: number, mid: number, right: number): number {
    // 从中点向左扩展的最大和
    let leftSum = -Infinity;
    let sum = 0;
    for (let i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }

    // 从中点向右扩展的最大和
    let rightSum = -Infinity;
    sum = 0;
    for (let i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }

    // 返回跨越中点的最大和
    return leftSum + rightSum;
}